package hot_100;

import java.util.Deque;
import java.util.LinkedList;

public class 单词搜索 {
    public static void main(String[] args) {

    }

    int n, m, len;
    int[][] fang = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int[][] vis;
    char[][] map;
    Deque<Character> deque = new LinkedList<>();
    String ans;

    public boolean exist(char[][] board, String word) {
        n = board.length;
        m = board[0].length;
        vis = new int[n + 1][m + 1];
        ans = word;
        len = word.length();
        map = board;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == word.charAt(0)) {
                    vis[i][j] = 1;
                    deque.addLast(map[i][j]);
                    if (Dfs(i, j, 1))
                        return true;
                    deque.removeLast();
                    vis[i][j] = 0;
                }
            }
        }
        return false;
    }

    public boolean Dfs(int x, int y, int l) {
        if (l >= len) {
            StringBuilder sb = new StringBuilder();
            for (Character c : deque) {
                sb.append(c);
            }
            return ans.contentEquals(sb);
        }
        for (int i = 0; i < 4; i++) {
            int dx = x + fang[i][0];
            int dy = y + fang[i][1];
            if (dx >= 0 && dx < n && dy >= 0 && dy < m && vis[dx][dy] == 0 && ans.charAt(l) == map[dx][dy]) {
                vis[dx][dy] = 1;
                deque.addLast(map[dx][dy]);
                if (Dfs(dx, dy, l + 1))
                    return true;
                deque.removeLast();
                vis[dx][dy] = 0;
            }
        }
        return false;
    }

}
